package algotithm.leetcode.dp.hot.test300;

/**
 * @author zhouyanxiang
 * @Date 2021-02-2021/2/9-22:26
 * @URL https://leetcode-cn.com/problems/longest-increasing-subsequence/
 * @Title 300. 最长递增子序列
 */
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {10,9,2,5,3,7,101,18};
        int i = solution.lengthOfLIS(nums);
        System.out.println(i);
    }

    public int lengthOfLIS(int[] nums) {
        if (nums.length == 1) {
            return 1;
        }
        int max = 0;
        int[] dp = new int[nums.length];
        dp[0] = 1;
        for (int i = 1; i < nums.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i],dp[j] + 1);
                }
            }
            max = Math.max(max,dp[i]);
        }
        return max;
    }
}

//class Solution {
//    public int lengthOfLIS(int[] nums) {
//        int len = nums.length;
//        int ind = 0;
//        int[] lower = new int[len];
//        for (int i = 0; i < len; i++) {
//            int point = lowerBound(lower,ind,nums[i]);
//            lower[point] = nums[i];
//            if (point == ind) {
//                ind++;
//            }
//        }
//        return ind;
//    }
//    public static int lowerBound(int[] lower, int len, int num) {
//        int l = 0, r = len - 1;
//        while (l <= r) {
//            int mid = (l + r) >> 1;
//            if (lower[mid] < num) {
//                l = mid + 1;
//            } else {
//                r = mid - 1;
//            }
//        }
//        return l;
//    }
//}